package a09_贪心算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>
 * a19_划分字母区间复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/2/27
 */
public class a19_划分字母区间复习2 {

    public static void main(String[] args) {
        a19_划分字母区间复习2 test = new a19_划分字母区间复习2();
        System.out.println(test.partitionLabels("ababcc"));
    }

    public List<Integer> partitionLabels(String s) {
        char[] chars = s.toCharArray();
        List<Integer> result = new ArrayList<>();

        //统计每个字符的最远的索引
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            map.put(chars[i],i);
        }


        //如果当前遍历的索引是当前字符的最远索引，需要截取
        //上面方案不行，因为中间的元素有可能最远索引不是rightIdx
        int leftIdx = 0;
        int rightIdx = 0;
        int maxIdx = 0;
        while (rightIdx < chars.length){
            maxIdx = Math.max(maxIdx,map.get(chars[rightIdx]));
            if(rightIdx == maxIdx){
                //截取
                result.add(rightIdx-leftIdx+1);
                rightIdx++;
                leftIdx = rightIdx;
            }else {
                //继续
                rightIdx++;
            }
        }

        return result;
    }
}
